#pragma once
#include "vector"
#include "set"
#include "hash_set"
#include "list"
#include "GridGraph.h"
//#include "SnapshotItem.h"
#include "Memory.h"

class PathFindingAlgorithm
{
public:
	PathFindingAlgorithm(GridGraph graph, int sizeX, int sizeY,
		int sx, int sy, int ex, int ey)
	{
		this->graph = graph;
		this->sizeX = sizeX;
		this->sizeXplusOne = sizeX + 1;
		this->sizeY = sizeY;
		this->sx = sx;
		this->sy = sy;
		this->ex = ex;
		this->ey = ey;
	}
	~PathFindingAlgorithm(){};
public:
	 void initialiseMemory(int size, float defaultDistance, int defaultParent, bool defaultVisited) {
		usingStaticMemory = true;
		ticketNumber = Memory::initialise(size, defaultDistance, defaultParent, defaultVisited);   
	}

	/**
	* Call to start tracing the algorithm's operation.
	*/
	void startRecording() {
		recordingMode = true;
	}

	/**
	* Call to stop tracing the algorithm's operation.
	*/
	void stopRecording() {
		recordingMode = false;
	}

	/**
	* @return retrieve the trace of the algorithm that has been recorded.
	*/
	//std::vector<std::list<SnapshotItem>> retrieveSnapshotList() {
	//	return snapshotList;
	//}

	/**
	* Call this to compute the path.
	*/
	virtual void computePath()=0;

	/**
	* @return retrieve the path computed by the algorithm
	*/
	virtual std::vector<std::pair<int, int>> getPath() = 0;

	/**
	* @return directly get path length without computing path.
	* Has to run fast, unlike getPath.
	*/
	virtual float getPathLength()=0;


	int toOneDimIndex(int x, int y) {
		return graph.toOneDimIndex(x, y);
	}

	int toTwoDimX(int index) {
		return graph.toTwoDimX(index);
	}

	int toTwoDimY(int index) {
		return graph.toTwoDimY(index);
	}

	//void saveSearchSnapshot() {
	//	if (snapshotCountdown > 0) {
	//		snapshotCountdown--;
	//		return;
	//	}
	//	snapshotCountdown = SNAPSHOT_INTERVAL;

	//	snapshotList.push_back(computeSearchSnapshot());
	//}

	//void maybeSaveSearchSnapshot() {
	//	if (recordingMode) {
	//		if (usingStaticMemory && ticketNumber != Memory::currentTicket())
	//			//erro
	//			return;
	//		saveSearchSnapshot();
	//	}
	//}

	//std::list<SnapshotItem> getCurrentSearchSnapshot() {
	//	return computeSearchSnapshot();
	//}

	bool isRecording() {
		return recordingMode;
	}




	//void addSnapshot(std::list<SnapshotItem> snapshotItemList) {
	//	snapshotList.push_back(snapshotItemList);
	//}

	int goalParentIndex() {
		return toOneDimIndex(ex, ey);
	}

	int getParent(int index) {
		if (usingStaticMemory) return Memory::Getparent(index);
		else return parent[index];
	}

	void setParent(int index, int value) {
		if (usingStaticMemory) Memory::setParent(index, value);
		else parent[index] = value;
	}

	int getSize() {
		if (usingStaticMemory) return Memory::Getsize();
		else return parent.size();
	}

	//std::list<SnapshotItem> computeSearchSnapshot() {
	//	std::list<SnapshotItem> list;
	//	int current = goalParentIndex();
	//	std::set<int> finalPathSet;
	//	if (getParent(current) >= 0) {
	//		while (current >= 0) {
	//			finalPathSet.insert(current);
	//			current = getParent(current);
	//		}
	//	}

	//	int size = getSize();
	//	for (int i = 0; i<size; i++) {
	//		if (getParent(i) != -1) {
	//			if (!finalPathSet.empty() && finalPathSet.find(i) != finalPathSet.end()) {
	//				list.push_back(SnapshotItem::generate(snapshotEdge(i)));
	//			}
	//			else {
	//				list.push_back(SnapshotItem::generate(snapshotEdge(i)));
	//			}
	//		}
	//		std::vector<int> vertexSnapshot = snapshotVertex(i);
	//		if (vertexSnapshot.at(0) != 0 && vertexSnapshot.at(1) != 0) {
	//			list.push_back(SnapshotItem::generate(vertexSnapshot));
	//		}
	//	}

	//	return list;
	//}

	std::vector<int> snapshotEdge(int endIndex) {
		std::vector<int> edge;
		edge.resize(4);
		int startIndex = getParent(endIndex);
		edge[2] = toTwoDimX(endIndex);
		edge[3] = toTwoDimY(endIndex);
		if (startIndex < 0) {
			edge[0] = edge[2];
			edge[1] = edge[3];
		}
		else {
			edge[0] = toTwoDimX(startIndex);
			edge[1] = toTwoDimY(startIndex);
		}

		return edge;
	}

	std::vector<int> snapshotVertex(int index) {
		std::vector<int> edge;
		edge.resize(2,0);

		if (selected(index)) {
			edge[0] = toTwoDimX(index);
			edge[1] = toTwoDimY(index);
		}
		return edge;
	}

	bool selected(int index) {
		return false;
	}

	//void inheritSnapshotListFrom(PathFindingAlgorithm*algo) {
	//	this->snapshotList = algo->snapshotList;

	//}
protected:
	int SNAPSHOT_INTERVAL = 0;
	int snapshotCountdown = 0;
	//std::vector<std::list<SnapshotItem>> snapshotList;
	GridGraph graph;

	std::vector<int> parent;
	int sizeX;
	int sizeXplusOne;
	int sizeY;

	int sx;
	int sy;
	int ex;
	int ey;
	int ticketNumber = -1;
	bool recordingMode;
	bool usingStaticMemory = false;
};

